package lc;

import ch2linkedlist.ListNode;

class RandomListNode extends ListNode {
	RandomListNode random;

	RandomListNode(int x) {
		super(x);
	}
};

public class CopyListWithRandomPointer {
	public RandomListNode copyRandomList(RandomListNode head) {
		if (head == null) {
			return null;
		}
		
		RandomListNode n = head;
		while (n != null) {
			RandomListNode node = new RandomListNode(n.val);
			node.next = n.next;
			n.next = node;
			n = (RandomListNode) n.next.next;
		}
		
		n = head;
		while (n != null) {
			RandomListNode random = n.random;
			RandomListNode newNode = (RandomListNode) n.next;
			newNode.random = random == null ? null : (RandomListNode) random.next;
			n = (RandomListNode) n.next.next;
		}

		n = head;
		RandomListNode newHead = (RandomListNode) head.next;
		while (n!=null) {
			RandomListNode m = (RandomListNode) n.next;
			RandomListNode tmp = (RandomListNode) n.next.next;
			n.next = tmp;
			m.next = tmp == null ? null : tmp.next;
			n = tmp;
		}
		
		return newHead;
	}

	public static void main(String ...strings) {
		RandomListNode head = new RandomListNode(-1);
		CopyListWithRandomPointer sol = new CopyListWithRandomPointer();
		sol.copyRandomList(head);
	}
	
}
